1. Field of the Invention
The present invention relates to cryptographic and error correction techniques for information security, and in particular relates to computation techniques which use extension fields and systems of equations.
2. Description of the Prior Art
Secret communication or digital signature techniques have increasingly been used in data communication in recent years.
Secret communication techniques allow communication to be performed without the communicated content being revealed to third parties. Digital signature techniques, meanwhile, enable the recipient to verify whether the communicated content is valid or whether the information is from the stated sender. Such secret communication or digital signature techniques use a cryptosystem called public key cryptography. Public key cryptography provides a convenient method for managing the separate encryption keys of many users, and so has become a fundamental technique for performing communication with a large number of users.
In the public key cryptography, different keys are used for encryption and decryption, with the decryption key being kept secret and the encryption key being made public. Here, one of the founding principles for the security of public key cryptography is the so-called discrete logarithm problem. Representative examples of the discrete logarithm problem are problems based on finite fields and problems based on elliptic curves. Such problems are described in detail in Neal Koblitz (1987), A Course in Number Theory and Cryptography, Springer-Verlag.
(Elliptic Curve Discrete Logarithm Problem)
The elliptic curve discrete logarithm problem is the following.
Let E be an elliptic curve defined over a finite field GF(q) (q=pn, p a prime, n a positive integer), with a point G on the elliptic curve E, given when the order of E is divisible by a large prime, being set as a base point. This being so, the problem is to find an integer x such thatY=x*G                 where Y is a given point on E, if such an integer x exists.        
In this specification, the operator * represents elliptic curve exponentiation, so that x*G means G is added to itself x times on E. Also, GF(q) is an extension field of a finite field GF(p). For details about extension fields, see T. Okamoto & H. Yamamoto (1997), Modern Encryption, Mathematics of Information Sciences Series, Sangyo Tosho, pp. 26–28.
(Prior Art 1: ElGamal Signature Scheme which Uses the Elliptic Curve Discrete Logarithm Problem)
The ElGamal signature scheme using the elliptic curve discrete logarithm problem is described below with reference to FIG. 9.
In the figure, a device 310 used by a user A (hereafter, “user A 310”), a management center 320, and a device 330 used by a user B (hereafter, “user B 330”) are connected via a network.
Let p be a prime, q=pn, n be a positive integer, and E be an elliptic curve over a finite field GF(q), with G being a base point of E and r being the order of G. Which is to say, r is the smallest positive integer that satisfiesr*G=0                where 0 is the zero element in the additive group on the elliptic curve E.(1) Public Key Generation by the Management Center 320        
First, the management center 320 generates a public key YA of the user A 310 using the user A's secret key xA which has been informed beforehand, according to the equationYA=xA*G                 (S1, S2).        
The management center 320 announces the finite field GF(q), the elliptic curve E, and the base point G as system parameters, and reveals the public key YA of the user A 310 to the user B 330 (S3, S4).
(2) Signature Generation by the User A 310
The user A 310 generates a random number k (S5), calculatesR1=(rx,ry)=k*G                 (S6), and finds s satisfyings×k=m+rx×xAmod r         (S7) where m is a message to be sent from the user A 310 to the user B 330.        
The user A 310 sends the message m and the signature (R1,s) to the user B 330 (S8).
(3) Signature Verification by the User B 330
The user B 330 verifies the authenticity of the user A 310 by judging whethers*R1=m*G+rx*YA                 is true (S9).        
This equation is derived from
                              s          *                      R            1                          =                              [                                          (                                                      (                                          m                      +                                                                        r                          x                                                ×                                                  x                          A                                                                                      )                                    /                  k                                )                            ×              k                        ]                    *          G                                        =                              (                          m              +                                                r                  x                                ×                                  x                  A                                                      )                    *          G                                        =                              m            *            G                    +                                    (                                                r                  x                                ×                                  x                  A                                            )                        *            G                                                  =                              m            *            G                    +                                    r              x                        *                          Y              A                                          
In this ElGamal digital signature scheme using the elliptic curve discrete logarithm problem, elliptic curve exponentiation is repeatedly performed to generate the public key and the signature and to verify the signature.
For details on elliptic curve exponentiation, see “Efficient Elliptic Curve Exponentiation” in Miyaji, Ono & Cohen (1997), Advances in Cryptology-Proceedings of ICICS'97, Lecture Notes in Computer Science, Springer-Verlag, pp. 282–290 (hereafter “document 1”).
Let an elliptic curve be defined by an equation of the formy2=x3+a×x+b                 with some point P on the elliptic curve being represented by 2-tuple coordinates (x1,y1) called affine coordinates.        
Elliptic curve exponentiation in the 2-tuple coordinate is known to involve inverse operations on the finite field GF(q).
Document 1 makes brief mention of a 3-tuple coordinate called projective coordinate. 2-tuple coordinates can be transformed into corresponding 3-tuple coordinates as shown by(x1,y1)→(x1,y1,1)
Elliptic curve exponentiation in the 3-tuple coordinate involves no inverse operations on the finite field GF(q). Since inverting a finite field element generally takes considerable computation time, the 3-tuple coordinate is often used in elliptic curve exponentiation.
However, when transforming 3-tuple coordinates into corresponding 2-tuple coordinates as shown by(X,Y,Z)→(X/Z, Y/Z)                inversion on the finite field GF(q) is necessary.        
In step S6 in FIG. 9, for instance, after 2-tuple coordinates are transformed into 3-tuple coordinates, elliptic curve exponentiation is performed on the 3-tuple coordinates, and the resulting 3-tuple coordinates are transformed into corresponding 2-tuple coordinates. Inversion is needed in this transformation of the 3-tuple coordinates to the 2-tuple coordinates.
(Prior Art 2: Inversion in an Extension Field)
A conventional inverse operation on an extension field GF(q) (q=pn, p a prime, n a positive integer) is performed in the following way.
For simplicity's sake, a generator polynomial of the extension field GF(q) is set as f(g)=gn−β whose root is α, and an element of GF(q) to be inputted in the generator polynomial is set asx=x0+x1×α+ . . . +xn−1×αn−1 (1) Step 1
Based on the element x of GF(q), a system of equations for yi (i=0, 1, . . . , n−1)
                              x          0                ⁢                  y          0                    +              β        ⁢                                  ⁢                  x                      n            -            1                          ⁢                  y          1                    +              β        ⁢                                  ⁢                  x                      n            -            2                          ⁢                  y          2                    +      …      +              β        ⁢                                  ⁢                  x          1                ⁢                  y                      n            -            1                                =    1                                x          1                ⁢                  y          0                    +                          ⁢                        x          0                ⁢                  y          1                    +              β        ⁢                                  ⁢                  x                      n            -            1                          ⁢                  y          2                    +      …      +              β        ⁢                                  ⁢                  x          2                ⁢                  y                      n            -            1                                =    0                                x          2                ⁢                  y          0                    +                          ⁢                        x          1                ⁢                  y          1                    +                          ⁢                        x          0                ⁢                  y          2                    +      …      +              β        ⁢                                  ⁢                  x          3                ⁢                  y                      n            -            1                                =    0    ⋮                              x                      n            -            2                          ⁢                  y          0                    +                        x                      n            -            3                          ⁢                  y          1                    +                        x                      n            -            4                          ⁢                  y          2                    +      …      +              β        ⁢                                  ⁢                  x                      n            -            1                          ⁢                  y                      n            -            1                                =    0                                x                      n            -            1                          ⁢                  y          0                    +                        x                      n            -            2                          ⁢                  y          1                    +                        x                      n            -            3                          ⁢                  y          2                    +      …      +                        x          0                ⁢                  y                      n            -            1                                =    0                  is formed.(2) Step 2        
The solutions yk (k=0,1, . . . ,n−1) of the system of equations are sought.
(3) Step 3
From the solutions yk (k=0,1, . . . ,n−1), the inverseI=y0+y1α+ . . . yn−1αn−1                 is calculated. Hence the inverse of the element x in the extension field GF(q) is obtained.        
The validity of this inverse operation is shown below.
If the inverse I and the element x satisfy the relationshipxI=1 mod f(g)                then        
                    xI        =                ⁢                                            x              0                        ⁡                          (                                                y                  0                                +                                                      y                    1                                    ⁢                  α                                +                …                +                                                      y                                          n                      -                      1                                                        ⁢                                      α                                          n                      -                      1                                                                                  )                                +                                                ⁢                                            x              1                        ⁢                          α              ⁡                              (                                                      y                    0                                    +                                                            y                      1                                        ⁢                    α                                    +                  …                  +                                                            y                                              n                        -                        1                                                              ⁢                                          α                                              n                        -                        1                                                                                            )                                              +                                                ⁢                                                            x                2                            ⁢                                                α                  2                                ⁡                                  (                                                            y                      0                                        +                                                                  y                        1                                            ⁢                      α                                        +                    …                    +                                                                  y                                                  n                          -                          1                                                                    ⁢                                              α                                                  n                          -                          1                                                                                                      )                                                      +                                                  ⁢            ⋮                    ⁢                                          ⁢                                    x                              n                -                1                                      ⁢                                          α                                  n                  -                  1                                            ⁡                              (                                                      y                    0                                    +                                                            y                      1                                        ⁢                    α                                    +                  …                  +                                                            y                                              n                        -                        1                                                              ⁢                                          α                                              n                        -                        1                                                                                            )                                                                        and alsoαnβmod f(g)        
Accordingly,
                    xI        =                ⁢                                            x              0                        ⁡                          (                                                y                  0                                +                                                      y                    1                                    ⁢                  α                                +                …                +                                                      y                                          n                      -                      1                                                        ⁢                                      α                                          n                      -                      1                                                                                  )                                +                                                ⁢                                            x              1                        ⁡                          (                                                                    y                    0                                    ⁢                  α                                +                                                      y                    1                                    ⁢                                      α                    2                                                  +                …                +                                                      y                                          n                      -                      1                                                        ⁢                  β                                            )                                +                                                ⁢                                            x              2                        ⁡                          (                                                                    y                    0                                    ⁢                                      α                    2                                                  +                                                      y                    1                                    ⁢                                      α                    3                                                  +                …                +                                                      y                                          n                      -                      1                                                        ⁢                  αβ                                            )                                +                                                ⁢        ⋮                                        ⁢                              x                          n              -              1                                ⁡                      (                                                            y                  0                                ⁢                                  α                                      n                    -                    1                                                              +                                                y                  1                                ⁢                β                            +              …              +                                                y                                      n                    -                    1                                                  ⁢                                  α                                      n                    -                    2                                                  ⁢                β                                      )                                              which can be rearranged in ascending order of power of α into        
                    xI        =                ⁢                                            x              0                        ⁢                          y              0                                +                      β            ×                          x                              n                -                1                                      ×                                                  ⁢                          y              1                                +          …          +                      β            ⁢                                                  ⁢                          x              1                        ⁢                          y                              n                -                1                                              +                                                ⁢                              α            ⁡                          (                                                                    x                    1                                    ⁢                                      y                    0                                                  +                                                      x                    0                                    ×                                      y                    1                                                  +                …                +                                                      βx                    2                                    ⁢                                      y                                          n                      -                      1                                                                                  )                                +                                                ⁢                                            α              2                        ⁡                          (                                                                    x                    2                                    ⁢                                      y                    0                                                  +                                                      x                    1                                    ⁢                                      y                    1                                                  +                …                +                                  β                  ⁢                                                                          ⁢                                      x                    3                                    ⁢                                      y                                          n                      -                      1                                                                                  )                                +                                                ⁢        ⋮                                        ⁢                              α                          n              -              1                                ⁡                      (                                                            x                                      n                    -                    1                                                  ⁢                                  y                  0                                            +                                                x                                      n                    -                    2                                                  ⁢                                  y                  1                                            +              …              +                                                x                  0                                ⁢                                  y                                      n                    -                    1                                                                        )                              
From this equation and the relationship xI=1, the system of equations in step 1 is derived.
Therefore, calculating an inverse in the extension field GF(q) is equivalent to solving a system of equations on the basic field GF(p).
Though the foregoing example uses the generator polynomial of the form gn−β for simplicity's sake, a system of equations can be formed by the same procedure for a generator polynomial of ordinary form.
(Prior Art 3: Solution of a System of Equations on the Basic Field GF(p))
A conventional method for solving a system of equations on the basic field GF(p) is described below. This method is called Gaussian elimination. For details on Gaussian elimination, see K. Mizugami (1985), Mathematical Calculations by Computers, Introduction to Programming Series, Asakura Shoten, pp. 76˜82 (hereafter “document 2”).
A system of equations for xk (k=0, 1, 2, . . . , n−1)
                                                        a              11                        ⁢                          x              0                                +                                    a              12                        ⁢                          x              1                                +          …          +                                    a                              1                ⁢                n                                      ⁢                          x                              n                -                1                                                    =                  b          1                                                                            a              21                        ⁢                          x              0                                +                                    a              22                        ⁢                          x              1                                +          …          +                                    a                              2                ⁢                n                                      ⁢                          x                              n                -                1                                                    =                  b          2                                        ⋮        ⁢                                                                                              a              n1                        ⁢                          x              0                                +                                    a              n2                        ⁢                          x              1                                +          …          +                                    a              nn                        ⁢                          x                              n                -                1                                                    =                  b          n                                    is solved by Gaussian elimination in the following manner.(Step 1)        
A matrix M and a vector v are given respectively as
      M    =          (                                                  a              11                                                          a              12                                            …                                              a                              1                ⁢                n                                                                                        a              21                                                          a              22                                            …                                              a                              2                ⁢                n                                                                          ⋮                                ⋮                                ⋮                                ⋮                                                              a              n1                                                          a              n2                                            …                                              a              nn                                          )            v    =          (                                                  b              1                                                                          b              2                                                            ⋮                                                              b              n                                          )      
Meanwhile, a vector X is given as
  X  =      (                                        x            0                                                            x            1                                                •                                      •                                                  x                          n              -              1                                            )  
Then the above system of equations can be simply written asMX=v 
The matrix M an d the vector v are triangular transformed so as to put the matrix M into upper triangular form, as a result of which a matrix M′ and a vector v′ are generated. Here, the triangular transformation is such a transformation that changes all elements beneath the diagonal elements of a matrix to 0, and such a transformed matrix is called an upper triangular matrix.
The procedure of this conventional triangular transformation is explained below with reference to FIG. 10.
First, counter j is set at 1 (S21). Next, the inverse Ij of ajj is computed (S22), 1 is assigned to ajj (S23), and ajk=ajk×Ij and bj=bj×Ij are set for j+1≦k≦n (S24). Then counter i is set at j+1 (S25).
Following this, 0 is assigned to aij (S26), aik=aik−ajj×ajk is set for j+1≦k≦n (S27), and also bi=bi−aij×bj is set (S28). Then it is judged whether i=n (S29). If i≠n, counter i is incremented by 1 (S31) and the procedure returns to step S26. If i=n, it is judged whether j=n (S30). If j≠n, counter j is incremented by 1 and the procedure returns to step S22. If j=n, the procedure ends.
As a result, the matrix M′ and the vector v′ are obtained. The matrix M′ is a matrix whose diagonal elements are all 1 and whose elements beneath the diagonal elements are all 0.
The system of equations M′X=v′ and the system of equations MX=v have an equivalence relation.
Let the matrix M′ and the vector v′ be written respectively as
            M      ′        =          (                                                  c              11                                                          c              12                                            …                                              c                              1                ⁢                n                                                                                        c              21                                                          c              22                                            …                                              c                              2                ⁢                n                                                                          •                                •                                •                                •                                                •                                •                                •                                •                                                              c              n1                                                          c              n2                                            …                                              c              nn                                          )                  v      ′        =          (                                                  d              1                                                                          d              2                                                            •                                                •                                                              d              n                                          )      (Step 2)
The system of equations M′X=v′ is solved using the generated matrix M′ and vector v′, in the following way.
The values n−1, . . . , 1, 0 are set one by one in counter c in this order. For counter c,yc=dc+1                 is calculated when c=n−1, and        
      y    c    =            d              c        +        1              -                  ∑                  i          =                      c            +            1                                    n          -          1                    ⁢              (                              c                          c              +                              1                ⁢                                                                  ⁢                i                            +              1                                ×                      y                          i              -              1                                      )                            is calculated when c≠n−1.        